import java.util.HashMap;
import java.util.Map;

class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        // 记录 nums2 中各个数的出现次数
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums2) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        long count = 0;
        // 遍历 nums1
        for (int v : nums1) {
            // 寻找 v 的所有因子
            for (int i = 1; i * i <= v; i++) {
                if (v % i == 0) {
                    // 第一个因子 i
                    if (i * k <= v && v % (i * k) == 0) {
                        count += freqMap.getOrDefault(v / (i * k), 0);
                    }
                    // 第二个因子 v / i，避免重复
                    if (i != v / i && (v / i) * k <= v && v % ((v / i) * k) == 0) {
                        count += freqMap.getOrDefault(v / ((v / i) * k), 0);
                    }
                }
            }
        }
        return count;
    }
}
